#define  _CRT_SECURE_NO_WARNINGS 1
#include"heap.h";

void HeapInit(Heap* ph)
{
	ph->arr = (int*)malloc(sizeof(int) * 3);
	if (ph->arr == NULL)
	{
		perror("malloc fail");
		return;
	}
	ph->size = 0;
	ph->capacity = 3;
}

void Jumcapacity(Heap* ph)
{
	int* tmp = (int*)realloc(ph->arr, sizeof(int) * ph->capacity * 2);
	if (tmp == NULL)
	{
		perror("relloc fail");
		return;
	}
	ph->arr = tmp;
	ph->capacity = ph->capacity* 2;
}

void HeapPush(Heap* ph, HpDatatype x)
{
	if (ph->capacity == ph->size)
	{
		Jumcapacity(ph);
	}
	if (ph->size == 0)
	{
		ph->arr[ph->size] = x;
		ph->size++;
	}
	else
	{
		if (ph->size % 2 == 1)
		{
			if (ph->arr[(ph->size - 1) / 2] < x)
				HeapAdjust(ph, ph->size, x);
			else
			{
				ph->arr[ph->size] = x;
			}
		}
		else
		{
			if (ph->arr[(ph->size - 2) / 2] < x)
				HeapAdjust(ph, ph->size, x);
			else
			{
				ph->arr[ph->size] = x;
			}
		}
		ph->size++;
	}
}

void HeapAdjust(Heap* ph,int y , HpDatatype x)
{
	if (ph->size % 2 == 1)
	{
		while (ph->arr[(y-1)/2] < x)
		{
			ph->arr[y] = ph->arr[(y - 1) / 2];
			ph->arr[(y - 1) / 2] = x;
			y = (y - 1) / 2;
			if (y < 0)return;
		}
	}
	else
	{
		while (ph->arr[(y - 2) / 2] < x)
		{
			ph->arr[y] = ph->arr[(y - 2) / 2];
			ph->arr[(y - 2) / 2] = x;
			y = (y - 2) / 2;
			if (y < 0)return;
		}
	}
}

void HeapDestroy(Heap* ph)
{
	free(ph->arr);
	ph->arr = NULL;
	ph->size = 0;
	ph->capacity = 0;
}